Search Results

1. E. Hyytiä, T. Tirronen and J. Virtamo, Optimal Degree Distribution for LT Codes with Small Message Length, in INFOCOM 2007, 26th IEEE International Conference on Computer Communications, pp. 2576-2580, 2007, Anchorage, Alaska, USA (bib)

   Abstract: Fountain codes provide an efficient way to transfer information over erasure channels. We give an exact performance analysis of a specific type of fountain codes, called LT codes, when the message length N is small. Two different approaches are developed. In a Markov chain approach the state space explosion, even with reduction based on permutation isomorphism, limits the analysis to very short messages, N <= 4. An alternative combinatorial method allows recursive calculation of the probability of decoding after N received packets. The recursion can be solved symbolically for values of N up to 10 and numerically up to values of the order of N = 30. Examples of optimization results give insight into the nature of the problem. In particular, we argue that a few conditions are sufficient to define an almost optimal LT encoding.